#include <stdio.h>
#include <process.h>
#include <malloc.h>
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// -------------线性表的动态分配顺序存储结构------------
#define LIST_INIT_SIZE 100  // 线性表存储空间的初始分配量
#define LISTINCREMENT 10  // 线性表存储空间的分配增量
// Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
//定义ElemType数据类型
typedef int ElemType;
typedef struct {
	ElemType *elem;
	int length;
	int listsize;
}SqList;
// 函数声明
Status InitList(SqList *);
Status ListInsert(SqList *, int, ElemType);
Status ListDelete(SqList *L, int i, ElemType *e);
void ListPrint(SqList *);


// 主函数
int main(){
	SqList *list = (SqList *) malloc(sizeof(SqList));
	ElemType e;
	InitList(list);
	ListInsert(list, 1, 10);
	ListInsert(list, 2, 20);
	ListInsert(list, 3, 30);
	ListPrint(list);
	ListDelete(list, 2, &e);
	printf("删除的元素值为%d\n", e);
	ListPrint(list);
	return 0;
}

// 函数定义
// 初始化线性表
Status InitList(SqList *L){
	// 构造一个空的线性表L
	L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!L->elem)
		exit(OVERFLOW);
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return OK;
}

// 线性表插入方法
Status ListInsert(SqList *L, int i, ElemType e){
	// 在顺序线性表L中第i个位置之前插入新的元素e
	// i的合法值为1<=i<=ListLength(L) + 1
	if (i <1 || i>L->length+1)	// i值不合法
		return ERROR;
	if(L->length >= L->listsize){	// 当前存储空间已满，增加分配
		ElemType* newBase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT)*sizeof(ElemType));
		if(!newBase)
			exit(OVERFLOW);
		L->elem = newBase;
		L->listsize += LISTINCREMENT;
	}
	ElemType *q = &(L->elem[i-1]), *p = &(L->elem[L->length-1]);
	for(; p>=q;p--)
		*(p+1) = *p;
	*q = e;
	L->length++;
	return OK;
}

// 删除第i个元素
Status ListDelete(SqList *L, int i, ElemType *e){
    // 在顺序线性表L中删除第i个元素，并用e返回其值
    // i的合法值为1<=i<=ListLength(L)
    if((i<1)||(i>L->length))
        return ERROR;
    ElemType *p = &(L->elem[i-1]), *q = &(L->elem[L->length-1]);
    *e = *p;
    for(++p; p<=q; ++p)
        *(p-1) = *p;
    L->length--;
    return OK;
}

// 打印线性表
void ListPrint(SqList *L){
	if(L->length > 0){
		ElemType *q = &(L->elem[0]), *p = &(L->elem[L->length-1]);
		for(; q<=p; q++)
			printf("%5d", *q);
		printf("\n");
	}
}
